package com.wenhai.liuyubobobo.imooc.tree;

/**
 * 二叉搜索树
 *
 * @author wenhai
 * @date 2021/3/5
 */
public class BST<E extends Comparable<E>> {
    private Node<E> root;
    private int size;


    public int size() {
        return this.size;
    }


    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 使用递归添加元素
     *
     * @param e 被添加的元素
     */
    public void addR(E e) {
        root = addR(root, e);
    }


    public void add(E e) {
        if (root == null) {
            root = new Node<>(e);
            size++;
            return;
        }
        Node<E> child  = root;
        Node<E> parent = root;
        int     cmp    = 0;
        while (child != null) {
            parent = child;
            cmp = child.element.compareTo(e);
            if (cmp > 0) {
                child = child.left;
            } else if (cmp < 0) {
                child = child.right;
            } else {
                return;
            }
        }

        child = new Node<>(e);
        if (cmp > 0) {
            parent.right = child;
        } else {
            parent.left = child;
        }
        size++;
    }


    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node<E> node, E e) {
        if (node == null) {
            return false;
        }

        int cmp = node.element.compareTo(e);
        if (cmp == 0) {
            return true;
        } else if (cmp > 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    private Node<E> addR(Node<E> node, E e) {
        if (node == null) {
            size++;
            return new Node<>(e);
        }
        if (node.element.compareTo(e) > 0) {
            node.left = addR(node.left, e);
        }
        if (node.element.compareTo(e) < 0) {
            node.right = addR(node.right, e);
        }
        return node;
    }


    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;

        Node(E element) {
            this.element = element;
        }
    }
}
